package 每日一题;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class 面试题16_25_LRU缓存 {

    /**
     * 设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。
     * 缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。
     * 当缓存被填满时，它应该删除最近最少使用的项目。
     * 它应该支持以下操作： 获取数据 get 和 写入数据 put 。
     * 获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
     * 写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，
     * 它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
     *
     *示例:
     *LRUCache cache = new LRUCache( 2  缓存容量  );
     *cache.put(1,1);
     *cache.put(2,2);
     *cache.get(1);       // 返回  1
     *cache.put(3,3);    // 该操作会使得密钥 2 作废
     *cache.get(2);       // 返回 -1 (未找到)
     *cache.put(4,4);    // 该操作会使得密钥 1 作废
     *cache.get(1);       // 返回 -1 (未找到)
     *cache.get(3);       // 返回  3
     *cache.get(4);       // 返回  4
     */

    //解题要点:虚拟节点+四个抽离方法
    private static class LRUCache{

        private Map<Integer,ListNode> map;
        //为了使操作更方便
        private ListNode firstNode;//头节点
        private ListNode tailNode;//尾节点
        private int capacity;
        private int currentCapacity;

        public LRUCache(int capacity) {
            this.map=new HashMap<>();
            this.firstNode=new ListNode(null,null,-1,-1);
            this.tailNode=new ListNode(null,null,-1,-1);
            firstNode.next=tailNode;
            tailNode.last=firstNode;
            this.capacity=capacity;
        }

        public int get(int key) {
            ListNode listNode = map.get(key);
            if(listNode==null){
                return -1;
            }
            //维护到头并且返回
            moveNodeToHead(listNode);
            return listNode.value;
        }

        public void put(int key, int value) {
            ListNode listNode = map.get(key);
            if(listNode==null){
                //添加到头部
                addNodeToHead(new ListNode(key,value));
                currentCapacity++;
            }else{
                //修改并且移到头部
                listNode.value=value;
                moveNodeToHead(listNode);
            }
            if(currentCapacity >capacity){
                removeTailNode();
            }
        }

        //添加到头部
        private void addNodeToHead(ListNode listNode){
            listNode.last=firstNode;
            listNode.next=firstNode.next;
            firstNode.next.last=listNode;
            firstNode.next=listNode;
            map.put(listNode.key,listNode);
        }

        //移除尾部
        private void removeTailNode(){
            map.remove(tailNode.last.key);
            removeNode(tailNode.last);
            currentCapacity--;
        }

        //移动到头部
        private void moveNodeToHead(ListNode listNode){
            removeNode(listNode);
            addNodeToHead(listNode);
        }

        //脱离一个节点
        private void removeNode(ListNode listNode){
            listNode.last.next=listNode.next;
            listNode.next.last=listNode.last;
            listNode.last=null;
            listNode.next=null;
        }

        private void printNodeList(){
            ListNode n=firstNode.next;
            while (n!=null&&n.value!=-1){
                System.out.print(n.value+"|");
                n=n.next;
            }
            System.out.println();
        }

        private class ListNode{
            public ListNode last;
            public ListNode next;
            public int key;
            public int value;
            public ListNode(ListNode last, ListNode next, int key, int value) {
                this.last = last;
                this.next = next;
                this.key = key;
                this.value = value;
            }

            public ListNode(int key, int value) {
                this.key = key;
                this.value = value;
            }
        }

    }

    public static void main(String[] args) {
        面试题16_25_LRU缓存.LRUCache n=new 面试题16_25_LRU缓存.LRUCache(2);
        n.put(1,1);
        n.put(2,2);
        n.printNodeList();
        n.get(1);
        n.printNodeList();
        n.put(3,3);
        n.printNodeList();
        n.get(2);
        n.printNodeList();
        n.put(4,4);
        n.printNodeList();
        n.get(1);
        n.get(3);
        n.get(4);
    }

}
